package org.piggy.core.algorithm;

import java.util.HashMap;
import java.util.Map;

public class PathTrie<V> {
    private final TrieNode<V> root = new TrieNode<>();

    /**
     * 插入一个路由前缀，如 "/api/user"
     */
    public void insert(String path, V data) {
        if (path == null || !path.startsWith("/")) {
            throw new IllegalArgumentException("Path must start with '/'");
        }

        String[] parts = splitPath(path);
        TrieNode<V> current = root;

        for (String part : parts) {
            current.children.putIfAbsent(part, new TrieNode<>());
            current = current.children.get(part);
        }

        current.isEnd = true;
        current.data = data;
    }

    /**
     * 查找最长匹配的路由数据
     * 例如：path="/api/user/123"，会匹配 "/api/user"（如果存在）
     */
    public V match(String path) {
        if (path == null || !path.startsWith("/")) {
            return null;
        }

        String[] parts = splitPath(path);
        TrieNode<V> current = root;
        V bestMatch = null; // 记录最后一个 isEnd 的 data

        for (String part : parts) {
            TrieNode<V> next = current.children.get(part);
            if (next == null) {
                break; // 路径中断，无法继续匹配
            }
            current = next;
            if (current.isEnd) {
                bestMatch = current.data; // 更新为更长的匹配
            }
        }

        return bestMatch;
    }

    /**
     * 辅助方法：将路径按 "/" 切分，过滤空字符串
     * "/api/user" → ["api", "user"]
     */
    private String[] splitPath(String path) {
        // 去掉开头的 "/"，然后按 "/" 分割
        String trimmed = path.substring(1);
        if (trimmed.isEmpty()) {
            return new String[0];
        }
        return trimmed.split("/");
    }

    static class TrieNode<V> {
        // 子节点：按路径段（如 "user"）索引
        Map<String, TrieNode<V>> children = new HashMap<>();

        // 是否为一个完整路由终点（如 /api/user）
        boolean isEnd = false;

        // 对应的数据（如 Handler、Service 等）
        V data = null;
    }

    public static void main(String[] args) {
        PathTrie<String> router = new PathTrie<>();

        // 注册路由
        router.insert("/api", "API服务");
        router.insert("/api/user", "用户服务");
        router.insert("/api/order", "订单服务");
        router.insert("/health", "健康检查");

        // 测试匹配
        System.out.println(router.match("/api/user/123"));   // 输出: 用户服务
        System.out.println(router.match("/api/order"));      // 输出: 订单服务
        System.out.println(router.match("/api/11"));         // 输出: API服务
        System.out.println(router.match("/health/check"));   // 输出: 健康检查
        System.out.println(router.match("/unknown"));        // 输出: null
        System.out.println(router.match("/api/user"));       // 输出: 用户服务
    }
}


